from functools import reduce
import operator

from algorithm.comparison import compare_list
from algorithm.list import inplace_map
from number_theory.gcd import gcd_list
from polynomial.polynomial import Polynomial

__all__ = ["PolynomialZ"]



class PolynomialZ(Polynomial):

    __slots__ = ("_coeff",)
    member_type = int
    zero = 0
    one = 1

    def __lt__(self, other):
        l1 = len(self._coeff)
        l2 = len(other._coeff)
        if l1 < l2:
            return True
        elif l1 > l2:
            return False
        for x, y in zip(reversed(self._coeff), reversed(other._coeff)):
            comparison = compare_list(abs, lambda x: x)(x, y)
            if comparison < 0:
                return True
            elif comparison > 0:
                return False
        return False

    def primitive(self):
        if self:
            g = gcd_list(self._coeff)
            if self._coeff[-1] < 0:
                g = -g
            return type(self)(x // g for x in self._coeff)
        else:
            return type(self)()

    def to_primitive(self):
        if self:
            g = gcd_list(self._coeff)
            if self._coeff[-1] < 0:
                g = -g
            if g != 1:
                inplace_map(lambda x: operator.ifloordiv(x, g), self._coeff)
        return self

    def __divmod__(self, other):
        if not other:
            raise ZeroDivisionError
        quotient = PolynomialZ()
        remainder = PolynomialZ(self)
        l2 = len(other._coeff)
        deg_diff = len(remainder._coeff) - l2
        if deg_diff >= 0:
            quotient._coeff = [0] * (deg_diff + 1)
            while deg_diff >= 0:
                q, r = divmod(remainder._coeff[-1], other._coeff[-1])
                if r:
                    return q, r
                quotient._coeff[deg_diff] = q
                for deg, coeff in enumerate(other._coeff, deg_diff):
                    remainder._coeff[deg] -= q * coeff
                remainder.remove_leading_zeros()
                deg_diff = len(remainder._coeff) - l2
        return quotient, remainder

    def __floordiv__(self, other):
        return divmod(self, other)[0]

    def __mod__(self, other):
        if not other:
            raise ZeroDivisionError
        remainder = PolynomialZ(self)
        l2 = len(other._coeff)
        deg_diff = len(remainder._coeff) - l2
        if deg_diff >= 0:
            while deg_diff >= 0:
                q, r = divmod(remainder._coeff[-1], other._coeff[-1])
                if r:
                    return r
                for deg, coeff in enumerate(other._coeff, deg_diff):
                    remainder._coeff[deg] -= q * coeff
                remainder.remove_leading_zeros()
                deg_diff = len(remainder._coeff) - l2
        return remainder
